/**
 * Created with IntelliJ IDEA.
 * Description: leetcode: LCR 077. 排序链表
 * <a href="https://leetcode.cn/problems/7WHec2/description/">...</a>
 * User: DELL
 * Date: 2023-10-25
 * Time: 23:57
 */

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    /**
     * 解题思路: (归并法)
     * 总体上的思路就是先求出原链表的长度,之后从 gap = 1 开始,即先将原链表切分为每个
     * 均为 gap 个节点的有序小链表,之后就可以高效合并两个有序链表,之后将 gap *= 2
     * 然后不断归并,最后就可以得到有序的链表了,总体上本题难在如何很好的定义变量,
     * 使得上诉过程可以实现,其中较为复杂,建议画图多想.
     *
     * @param head
     * @return
     */
    public ListNode sortList(ListNode head) {
        // 判空处理
        if (head == null) {
            return null;
        }
        // 求出链表长度
        int length = 0;
        ListNode temp = head;
        while (temp != null) {
            length++;
            temp = temp.next;
        }
        ListNode newHead = new ListNode(-1, head);
        // 分组进行排序并归并
        for (int gap = 1; gap < length; gap <<= 1) {
            ListNode preCur = newHead;
            ListNode cur = newHead.next;
            while (cur != null) {
                // 先记录下第一组的头节点
                ListNode head1 = cur;
                // cur节点向后走 gap-1 步
                for (int i = 1; i < gap && cur != null; i++) {
                    cur = cur.next;
                }
                // 这里若 cur == null, 则表示只有左半组,则结束该轮排序
                // 这里要特别注意结束的时候要将左半组拼接到原链表上
                if (cur == null) {
                    preCur.next = head1;
                    break;
                }
                // 记录下下一组的头节点
                ListNode head2 = cur.next;
                // 将第一组链表切断
                cur.next = null;
                cur = head2;
                // cur节点继续向后走 gap-1 步
                for (int i = 1; i < gap && cur != null; i++) {
                    cur = cur.next;
                }
                // 这里如果cur不为null,即表示后续还要继续进行归并,需要记录下一组的开始
                // 而这里如果cur为null,则直接记录下一组开始为null即可
                ListNode next = null;
                if (cur != null) {
                    next = cur.next;
                    cur.next = null;
                }
                // 将cur跳转到下一组的开始
                cur = next;
                // 将两个有序链表归并
                preCur.next = merge(head1, head2);
                // 这里需要将preCur走到排序好的链表的结尾
                while (preCur.next != null) {
                    preCur = preCur.next;
                }
            }
        }
        return newHead.next;
    }

    private ListNode merge(ListNode left, ListNode right) {
        ListNode head = new ListNode();
        ListNode cur = head;
        while (left != null && right != null) {
            if (left.val <= right.val) {
                cur.next = left;
                cur = cur.next;
                left = left.next;
            } else {
                cur.next = right;
                cur = cur.next;
                right = right.next;
            }
        }
        if (left == null) {
            cur.next = right;
        } else {
            cur.next = left;
        }
        return head.next;
    }
}